/*
 **********************************************************
 *
 * Programme :	graphe.c
 *
 * ecrit par :	BAYRAMOV Matin & IBRAHIMLI Nihat
 *
 * resume : 		contient les entetes des fonctions utiles
 * 				pour la manupilation des graphes
 *
 * date :   		Feb 6, 2013
 *
 ***********************************************************
 */

#include <stdio.h>
#include <stdlib.h>

#include "liste.h"
#include "slist.h"

#include "stack.h"
#include "array.h"

#include "macros.h"
#include "heap.h"

#ifndef GRAPHE_H_
#define GRAPHE_H_

typedef struct TypGraphe {
	// max nombre de sommets de graphe
	int nbMaxSommets;
	// tableau des listes adjacaences
	TypVoisins** listesAdjacences;
} Graphe;

extern int * vertexColor;
extern int * vertexFather;

// Creation d'un graphe vide en fonction du nombre maximum de sommets
int creation(Graphe**, int);

// Insertion du sommet dans le graphe courant
int insertionSommet(Graphe*, int);

// Insert next vertex possible to graph and return it's index
int insertNextVertex(Graphe*);

// Insertion d'une arete du sommet courant au sommet voisin et de poids au graphe courant
int insertionArete(Graphe*, int, int, double, char);

// Suppression du sommet dans le graphe courant
int suppressionSommet(Graphe*, int);

// Suppression d'une arete du sommet courant au sommet voisin dans le graphe courant
int suppressionArete(Graphe*, int, int, char);

// Get a list of vertices that is adjacent to
TypVoisins* getAdjacentVertices(Graphe*, int);

// Implementation of depth-first search
int depthFirstSearch(Graphe*);

// Discover function of depth-first search
int discoverDFS(Graphe*, int);

// Libere la mémoire d'un graphe
int freeGraphe(Graphe**);

// Affichage du graphe courant
int affichageGraphe(Graphe*);

// Enregistre un graphe dans un fichier
int writeGrapheToFile(Graphe*, char*);

// Vérifie si le graphe est valide
int grapheEstValide(Graphe*);

// Vérifie si un sommet est valide
int sommetEstValide(int, int);

// Vérifie si le sommet est existe dans le graphe
int sommetEstExist(Graphe*, int);

// Vérifie si le poids est valide
int poidsEstValide(double);

int typeAreteValide(char);

// Tests whether there is an edge between vertices
int isAdjacent(Graphe*, int, int);

// Get the cost of edge between vertices
double getEdgeCost(Graphe*, int, int);

// Find the exact solution to TSP problem
int getExactTSPSolution(Graphe *);

int enumereCycles(List*, int, Stack*);

// Convert a graph to a matrix
int graphToMatrix(Graphe*, double***);

// Algorithm Christofides
int algorithmChristofides(Graphe*);

int shortenThePath(Graphe*, Graphe*, int);

// Get the number of outgoing edges
int countOutgoingEdges(Graphe *, int);

// Get the number of incoming edges
int countIncomingEdges(Graphe *, int);

// Set whether a vertex is odd (1) or even(0) degree
int oddOrEvenDegreeVertex(Graphe *, int *);

// check out if a vertex has been already selected
int vertexColorized(int*, int, int);

// find out the shortest path in the graph with nearest neighbor's method
int nearestNeighbor(Graphe*, int, int**);

//find out the shortest path in the graph by a factor of 2 less than the optimal
int less2Factor(Graphe*, int);

// compute minimum spanning tree 
int graphToARPM(Graphe*, Graphe*, int);

// create the minimum spanning tree 
void createTreeARPM(Graphe*, TypHeap);

// find out the shortest path in the graph with smallest detour's method
int smallestDetour(Graphe*, int, int, int, int**);

// get distance between the vertices that are in table 
double getPathSize(Graphe*, int*);

// get weight between fromVertex and toVertex
int getPoids(Graphe*, int, int);

// check out if all vertices are selected
int allVerticesSelected(int*, int);

// get new table that a vertex are insert in index + 1 
void copyVertexInArray(int*, int**, int, int, int);

// create a copy of an array
void copyArray(int*, int**, int);

#endif /* GRAPHE_H_ */
